package com.ry.day1129;

import java.util.ArrayList;
import java.util.List;

public class LK851_LC1449 {

    static class Solution {
        public int[] loudAndRich(int[][] richer, int[] quiet) {
            //图来解决
            //richer[i]={a,b}  表示a比b更有前，或者叫a->b有一条边
            //quiet[i]=k  表示i这个人的安静值是k
            // a->b  a->c   b->c      a: b c   b:c
            //nexts[0]={5,7,3}  表示0： 5 7 3   0比5 7 3 有钱
            //如果5最没钱 那么nexts[5]={}
            int n= quiet.length;
            List<List<Integer>> nexts= new ArrayList<>();
            for (int i = 0; i <n ; i++) {
                nexts.add(new ArrayList<>());
            }
            int[] degree = new int[n];
            for (int[] r : richer) {
                nexts.get(r[0]).add(r[1]);
                degree[r[1]]++;
            }
            //所有入度为0的点，入队列
            int[] zeroQueue = new int[n];
            int l=0;
            int r=0;
            for (int i = 0; i <n ; i++) {
                if(degree[i] ==0){
                    zeroQueue[r++] =i;
                }
            }
            //ans[i]=j  表示比i有钱的所有人里，j最安静
            int[] ans = new int[n];
            for (int i = 0; i < n; i++) {
                ans[i] =i;
            }

            while (l<r) { //如果队列不空
                //弹出一个入度为0的点
                int cur = zeroQueue[l++];
                //消除当前cur的影响
                for(int next: nexts.get(cur)){
                    //cur: 比cur更有钱 最安静的 ans[cur]
                    if(quiet[ans[next]] > quiet[ans[cur]]){
                        ans[next] = ans[cur];
                    }

                    if(--degree[next] ==0){
                        zeroQueue[r++] = next;
                    }
                }
            }

            return ans;
        }
    }

    public static void main(String[] args) {
        int[][] richer = {{1,0},{2,1},{3,1},{3,7},{4,3},{5,3},{6,3}};
        int[] quiet = {3,2,5,4,6,1,7,0};

        Solution obj = new Solution();
       show(obj.loudAndRich(richer,quiet));
    }
    public static void show(int[] arr){
        System.out.println();
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
}


/*
851. 喧闹和富有
中等
相关标签
相关企业
有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。

给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自洽（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。

现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最不安静的人（也就是安静值 quiet[y] 最小的人）。



示例 1：

输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
输出：[5,5,2,5,4,5,6,7]
解释：
answer[0] = 5，
person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
但是目前还不清楚他是否比 person 0 更有钱。
answer[7] = 7，
在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），
最安静（有较低安静值 quiet[x]）的人是 person 7。
其他的答案也可以用类似的推理来解释。
示例 2：

输入：richer = [], quiet = [0]
输出：[0]

 */
